package 剑指offer;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 数组中重复的数字
 */
public class Offer03_JZ50 {
    public static void main(String[] args) {
        int[] dup = new int[]{0};
        System.out.println(duplicate2(new int[]{6,3,2,0,2,5,0}, 7, dup));
        System.out.println(Arrays.toString(dup));
    }

    public static boolean duplicate(int numbers[],int length,int [] duplication) {
        if(length==0){
            return false;
        }
        Set<Integer> set = new HashSet<>();
        int i = 0;
        for(i=0; i<length; i++){
            if (numbers[i] >= length) {
                return false;
            } else if (set.contains(numbers[i])) {
                duplication[0] = numbers[i];
                return true;
            }
            set.add(numbers[i]);

        }
        return false;
    }

    public static boolean duplicate2(int numbers[],int length,int [] duplication) {
        if(length == 0) return false;
        for(int i=0; i<length; i++) {
            if(numbers[i]<0 || numbers[i]>=length) return false;
            while (numbers[i] != i) {
                if(numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }
}
